package com.example.demo.zaqizabatest.sortalgorithm;

/**
 *
 * 将一个大数组分成两个小数组去求解。
 *
 * 因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 O(NlogN)。
 *
 * @ClassName Up2DownMergeSort 自顶向下归并排序
 * @Author lys4134
 * @Date 2021/12/29 09:51:02
 * @Description Up2DownMergeSort
 * @Version 1.0
 **/
public class Up2DownMergeBaseSort<T extends Comparable<T>> extends MergeBaseSort<T> {

    @Override
    public void sort(T[] nums) {
        aux = (T[]) new Comparable[nums.length];
        sort(nums, 0, nums.length - 1);
    }

    private void sort(T[] nums, int l, int h) {
        if (h <= l) {
            return;
        }
        int mid = l + (h - l) / 2;
        sort(nums, l, mid);
        sort(nums, mid + 1, h);
        merge(nums, l, mid, h);
    }
}